package com.aqie.easy.hash;

import java.util.*;

/**
 * 599 两个列表相同值得最小索引
 */
public class FindRestaurant {
    /**
     * 1. 108ms
     * @param list1
     * @param list2
     * @return
     */
    public String[] findRestaurant(String[] list1, String[] list2) {
        Map<String, Integer> map = new HashMap<>();
        List<String> list = new ArrayList<>();
        int indexSum = Integer.MAX_VALUE;

        for (String aList1 : list1) {
            map.put(aList1, 1);
        }

        System.out.println(map);
        for (int i = 0; i < list2.length; i++){
            map.put(list2[i], map.getOrDefault(list2[i], 0) + 1);
            if (map.get(list2[i]) > 1) {
                int tmp = i + getIndex(list1, list2[i]);
                if (tmp < indexSum){
                    list.clear();
                    list.add(list2[i]);
                    indexSum = tmp;
                } else if (tmp == indexSum){
                    list.add(list2[i]);
                }

                System.out.println(tmp + " " + indexSum + " " + list);
            }
        }
        System.out.println(map);
        return list.toArray(new String[0]);
    }

    private int getIndex(String[] list, String target){
        for (int i = 0; i < list.length; i++){
            if (list[i].equals(target)) return i;
        }
        return -1;
    }


    /**
     * 2, 30ms  错误答案
     * @param list1
     * @param list2
     * @return
     */
    public String[] findRestaurant2(String[] list1, String[] list2) {
        List<String> ans = new ArrayList<>();
        int index = 0, top1 = 0, top2 = 0;  // 第一次匹配到list1 list2 的下标
        for (int i = 0; i < list1.length; i++){
            for (int j = 0; j < list2.length; j++){
                if (list1[i].equals(list2[j])){
                    ans.add(list1[i]);
                    index = i + j;
                    top1 = i + 1;
                    top2 = j - 1;
                    // 中断比较 后面index 都大
                    i = list1.length;
                    break;
                }
            }
        }

        while (top1 < list1.length && top2 >= 0){
            if (list1[top1].equals(list2[top2])){
                ans.add(list1[top1]);
            }
            ++top1;
            --top2;
        }

        return ans.toArray(new String[0]);
    }

    public static void main(String[] args) {
        String[] list1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
        String[] list2={"Tapioca Express", "Burger King", "Shogun"};
        // String[] list2 = {"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};
        /*String[] list1 = {"a", "b", "c", "d"};
        String[] list2 = {"c", "b", "a", "d"};*/

        /*String[] list1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
        String[] list2 = {"KFC", "Shogun", "Burger King"};*/

        System.out.println(Arrays.toString(new FindRestaurant().findRestaurant(list1, list2)));
    }
}
